class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(),wordList.end());
        queue<string> toVisit;
        bfs(beginWord,dict,toVisit);
        int dist=2;
        while(!toVisit.empty()){
            int n=toVisit.size();
            for(int i=0;i<n;i++){
                string word=toVisit.front();
                toVisit.pop();
                if(word==endWord) return dist;
                bfs(word,dict,toVisit);
            }
            dist++;
        }
        return 0;
    }
    
    void bfs(string word, unordered_set<string>& dict, queue<string>& toVisit){
        dict.erase(word);
        for(int i=0;(int)i<word.size();i++){
            char letter=word[i];
            for(int k=0;k<26;k++){
                word[i]='a'+k;
                if(dict.find(word)!=dict.end()){
                    toVisit.push(word);
                    dict.erase(word);
                }
            }
            word[i]=letter;
        }
    }
    
};
